/**
 *  Copyright (C) 2008-2009  The Aceituna Project Team
 *  Portions of this code are Copyright(C) 2002-2007  The FreeCol Team (www.freecol.org).
 *
 *  This file is part of Aceituna Project.
 *
 *  Aceituna Project is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  Aceituna Project is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Aceituna Project.  If not, see <http://www.gnu.org/licenses/>.
 */

package com.aceitunaproject.mapdisplay.model.map;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

import com.aceitunaproject.mapdisplay.model.map.tile.Tile;

/**
 * An isometric map. The map is represented as a collection of tiles.
 */
public class Map {
    


    

    public static final int NUMBER_OF_DIRECTIONS = Direction.values().length;


    private Tile[][] tiles;

    
    
    

    /**
     * Create a new <code>Map</code> from a collection of tiles.
     * 
     * @param tiles
     *            The 2D array of tiles.
     */

    public Map(Tile[][] tiles) {
       
        this.tiles = tiles;
    }
   

    /**
     * Checks if the given <code>Tile</code> is adjacent to the edge of the
     * map.
     * 
     * @param tile
     *            The <code>Tile</code> to be checked.
     * @return <code>true</code> if the given tile is at the edge of the map.
     */
    public boolean isAdjacentToMapEdge(Tile tile) {
        for (Direction direction : Direction.values()) {
            if (getNeighbourOrNull(direction, tile) == null) {
                return true;
            }
        }
        return false;
    }

    

    /**
     * Returns the Tile at a requested position.
     * 
     * @param p
     *            The position.
     * @return The Tile at the given position.
     */
    public Tile getTile(Position p) {
        return getTile(p.getX(), p.getY());
    }

    /**
     * Returns the Tile at position (x, y). 'x' specifies a column and 'y'
     * specifies a row. (0, 0) is the Tile at the top-left corner of the Map.
     * 
     * @param x
     *            The x-coordinate of the <code>Tile</code>.
     * @param y
     *            The y-coordinate of the <code>Tile</code>.
     * @return The Tile at position (x, y) or <code>null</code> if the
     *         position is invalid.
     */
    public Tile getTile(int x, int y) {
        if (isValid(x, y)) {
            return tiles[x][y];
        } else {
            return null;
        }
    }

    /**
     * Sets the given tile the the given coordinates.
     * 
     * @param x
     *            The x-coordinate of the <code>Tile</code>.
     * @param y
     *            The y-coordinate of the <code>Tile</code>.
     * @param tile
     *            The <code>Tile</code>.
     */
    public void setTile(Tile tile, int x, int y) {
        tiles[x][y] = tile;
    }

    /**
     * Returns the width of this Map.
     * 
     * @return The width of this Map.
     */
    public int getWidth() {
        if (tiles == null) {
            return 0;
        } else {
            return tiles.length;
        }
    }

    /**
     * Returns the height of this Map.
     * 
     * @return The height of this Map.
     */
    public int getHeight() {
        if (tiles == null) {
            return 0;
        } else {
            return tiles[0].length;
        }
    }

    /**
     * Returns the neighbouring Tile of the given Tile in the given direction.
     * 
     * @param direction
     *            The direction in which the neighbour is located given t.
     * @param t
     *            The Tile to get a neighbour of.
     * @return The neighbouring Tile of the given Tile in the given direction.
     */
    public Tile getNeighbourOrNull(Direction direction, Tile t) {
        return getNeighbourOrNull(direction, t.getX(), t.getY());
    }

    /**
     * Returns the neighbouring Tile of the given Tile in the given direction.
     * 
     * @param direction
     *            The direction in which the neighbour is located given the base
     *            tile.
     * @param x
     *            The base tile X coordinate.
     * @param y
     *            The base tile Y coordinate.
     * @return The neighbouring Tile of the given coordinate in the given
     *         direction or null if invalid.
     */
    public Tile getNeighbourOrNull(Direction direction, int x, int y) {
        if (isValid(x, y)) {
            Position pos = getAdjacent(new Position(x, y), direction);
            return getTile(pos.getX(), pos.getY());
        } else {
            return null;
        }
    }

    /**
     * Returns all the tiles surrounding the given tile within the
     * given range. The center tile itself is not included.
     * 
     * @param t
     *            The tile that lies on the center of the tiles to return.
     * @param range
     *            How far away do we need to go starting from the center tile.
     * @return The tiles surrounding the given tile.
     */
    public List<Tile> getSurroundingTiles(Tile t, int range) {
        List<Tile> result = new ArrayList<Tile>();
        Position tilePosition = new Position(t.getX(), t.getY());
        Iterator<Position> i = (range == 1) ? getAdjacentIterator(tilePosition)
                : getCircleIterator(tilePosition, true, range);

        while (i.hasNext()) {
            Position p = i.next();
            if (!p.equals(tilePosition)) {
                result.add(getTile(p));
            }
        }

        return result;
    }

   

    /**
     * Gets an <code>Iterator</code> of every <code>Tile</code> on the map.
     * 
     * @return the <code>Iterator</code>.
     */
    public WholeMapIterator getWholeMapIterator() {
        return new WholeMapIterator();
    }
    
    /**
     * Gets the position adjacent to a given position, in a given
     * direction.
     *
     * @param position The position
     * @param direction The direction (N, NE, E, etc.)
     * @return Adjacent position
     */
     public static Position getAdjacent(Position position, Direction direction) {
         int x = position.x + ((position.y & 1) != 0 ?
                               direction.getOddDX() : direction.getEvenDX());
         int y = position.y + ((position.y & 1) != 0 ?
                               direction.getOddDY() : direction.getEvenDY());
         return new Position(x, y);
     }

    /**
     * Get an adjacent iterator.
     * 
     * @param centerPosition
     *            The center position to iterate around
     * @return Iterator
     */
    public Iterator<Position> getAdjacentIterator(Position centerPosition) {
        return new AdjacentIterator(centerPosition);
    }

    /**
     * Get a border adjacent iterator.
     * 
     * @param centerPosition
     *            The center position to iterate around
     * @return Iterator
     */
    public Iterator<Position> getBorderAdjacentIterator(Position centerPosition) {
        return new BorderAdjacentIterator(centerPosition);
    }

    /**
     * Get a flood fill iterator.
     * 
     * @param centerPosition
     *            The center position to iterate around
     * @return Iterator
     */
    public Iterator<Position> getFloodFillIterator(Position centerPosition) {
        return new CircleIterator(centerPosition, true, Integer.MAX_VALUE);
    }

    /**
     * Get a circle iterator.
     * 
     * @param center
     *            The center position to iterate around
     * @param isFilled
     *            True to get all of the positions in the circle
     * @param radius
     *            Radius of circle
     * @return Iterator
     */
    public CircleIterator getCircleIterator(Position center, boolean isFilled,
            int radius) {
        return new CircleIterator(center, isFilled, radius);
    }

    /**
     * Checks whether a position is valid (within the map limits).
     * 
     * @param position
     *            The position
     * @return True if it is valid
     */
    public boolean isValid(Position position) {
        return isValid(position.x, position.y, getWidth(), getHeight());
    }

    /**
     * Checks whether a position is valid (within the map limits).
     * 
     * @param x
     *            X coordinate
     * @param y
     *            Y coordinate
     * @return True if it is valid
     */
    public boolean isValid(int x, int y) {
        return isValid(x, y, getWidth(), getHeight());
    }

    /**
     * Checks whether a position is valid.
     * 
     * @param position The position
     * @param width The width of the map.
     * @param height The height of the map.
     * @return <code>true</code> if the given position is 
     *        within the bounds of the map and <code>false</code> otherwise
     */
    public static boolean isValid(Position position, int width, int height) {
        return isValid(position.x, position.y, width, height);
    }
    
    /**
     * Checks if the given position is valid.
     * 
     * @param x The x-coordinate of the position.
     * @param y The y-coordinate of the position.
     * @param width The width of the map.
     * @param height The height of the map.
     * @return <code>true</code> if the given position is 
     *        within the bounds of the map and <code>false</code> otherwise
     */
    public static boolean isValid(int x, int y, int width, int height) {
        return x >= 0 && x < width && y >= 0 && y < height;
    }

    
    
    /**
     * Gets the distance in tiles between two map positions. With an isometric
     * map this is a non-trivial task. The formula below has been developed
     * largely through trial and error. It should cover all cases, but I
     * wouldn't bet my life on it.
     * 
     * @param position1
     *            The first position.
     * @param position2
     *            The second position.
     * @return Distance
     */
    public int getDistance(Position position1, Position position2) {
        return getDistance(position1.getX(), position1.getY(),
                position2.getX(), position2.getY());
    }

    /**
     * Gets the distance in tiles between two map positions.
     * 
     * @param ax
     *            Position A x-coordinate
     * @param ay
     *            Position A y-coordinate
     * @param bx
     *            Position B x-coordinate
     * @param by
     *            Position B y-coordinate
     * @return Distance
     */
    public int getDistance(int ax, int ay, int bx, int by) {
        int r = bx - ax - (ay - by) / 2;

        if (by > ay && ay % 2 == 0 && by % 2 != 0) {
            r++;
        } else if (by < ay && ay % 2 != 0 && by % 2 == 0) {
            r--;
        }

        return Math.max(Math.abs(ay - by + r), Math.abs(r));
    }

    
    

    public final class WholeMapIterator extends MapIterator {
        private int x;
        private int y;

        /**
         * Default constructor.
         */
        public WholeMapIterator() {
            x = 0;
            y = 0;
        }

        /**
         * Determine if the iterator has another position in it.
         * 
         * @return True of there is another position
         */
        public boolean hasNext() {
            return y < getHeight();
        }

        /**
         * Obtain the next position to iterate over.
         * 
         * @return Next position
         * @throws java.util.NoSuchElementException
         *             if last position already returned
         */
        @Override
        public Position nextPosition() throws NoSuchElementException {
            if (y < getHeight()) {
                Position newPosition = new Position(x, y);
                x++;
                if (x == getWidth()) {
                    x = 0;
                    y++;
                }
                return newPosition;
            }
            throw new NoSuchElementException("Iterator exhausted");
        }
    }

    private final class AdjacentIterator extends MapIterator {
        // The starting tile position
        private Position basePosition;
        // Index into the list of adjacent tiles
        private int x = 0;

        /**
         * The constructor to use.
         * 
         * @param basePosition
         *            The position around which to iterate
         */
        public AdjacentIterator(Position basePosition) {
            this.basePosition = basePosition;
        }

        /**
         * Determine if the iterator has another position in it.
         * 
         * @return True of there is another position
         */
        public boolean hasNext() {
            for (int i = x; i < 8; i++) {
                Position newPosition = getAdjacent(basePosition, directions[i]);
                if (isValid(newPosition))
                    return true;
            }
            return false;
        }

        /**
         * Obtain the next position to iterate over.
         * 
         * @return Next position
         * @throws NoSuchElementException
         *             if last position already returned
         */
        @Override
        public Position nextPosition() throws NoSuchElementException {
            for (int i = x; i < 8; i++) {
                Position newPosition = getAdjacent(basePosition, directions[i]);
                if (isValid(newPosition)) {
                    x = i + 1;
                    return newPosition;
                }
            }
            throw new NoSuchElementException("Iterator exhausted");
        }
    }

    /**
     * An interator returning positions in a spiral starting at a given center
     * tile. The center tile is never included in the positions returned, and
     * all returned positions are valid.
     * 
     * @see Map.Position
     */
    public final class CircleIterator extends MapIterator {
        private int radius;
        private int currentRadius;
        private Position nextPosition = null;
        // The current position in the circle with the current radius:
        private int n;

        /**
         * The constructor to use.
         * 
         * @param center
         *            The center of the circle
         * @param isFilled
         *            True to get all of the positions within the circle
         * @param radius
         *            The radius of the circle
         */
        public CircleIterator(Position center, boolean isFilled, int radius) {
            this.radius = radius;

            if (center == null) {
                throw new IllegalArgumentException("center must not be 'null'.");
            }

            n = 0;

            if (isFilled || radius == 1) {
                nextPosition = getAdjacent(center, Direction.NE);
                currentRadius = 1;
            } else {
                currentRadius = radius;
                nextPosition = center;
                for (int i = 1; i < radius; i++) {
                    nextPosition = getAdjacent(nextPosition, Direction.N);
                }
                nextPosition = getAdjacent(nextPosition, Direction.NE);
            }
            if (!isValid(nextPosition)) {
                determineNextPosition();
            }
        }

        /**
         * Returns the current radius of the circle.
         * 
         * @return The distance from the center tile this
         *         <code>CircleIterator</code> was initialized with.
         */
        public int getCurrentRadius() {
            return currentRadius;
        }

        /**
         * Finds the next position.
         */
        private void determineNextPosition() {
            boolean positionReturned = (n != 0);
            do {
                n++;
                final int width = currentRadius * 2;
                if (n >= width * 4) {
                    currentRadius++;
                    if (currentRadius > radius) {
                        nextPosition = null;
                    } else if (!positionReturned) {
                        nextPosition = null;
                    } else {
                        n = 0;
                        positionReturned = false;
                        nextPosition = getAdjacent(nextPosition, Direction.NE);
                    }
                } else {
                    int i = n / width;
                    Direction direction;
                    switch (i) {
                    case 0:
                        direction = Direction.SE;
                        break;
                    case 1:
                        direction = Direction.SW;
                        break;
                    case 2:
                        direction = Direction.NW;
                        break;
                    case 3:
                        direction = Direction.NE;
                        break;
                    default:
                        throw new IllegalStateException("i=" + i + ", n=" + n
                                + ", width=" + width);
                    }
                    nextPosition = getAdjacent(nextPosition, direction);
                }
            } while (nextPosition != null && !isValid(nextPosition));
        }

        /**
         * Determine if the iterator has another position in it.
         * 
         * @return <code>true</code> of there is another position and
         *         <code>false</code> otherwise.
         */
        public boolean hasNext() {
            return nextPosition != null;
        }

        /**
         * Obtains the next position.
         * 
         * @return The next position. This position is guaratied to be
         *         {@link Map#isValid(net.sf.freecol.common.model.Map.Position) valid}.
         */
        @Override
        public Position nextPosition() {
            if (nextPosition != null) {
                final Position p = nextPosition;
                determineNextPosition();
                return p;
            } else {
                return null;
            }
        }
    }

    private final class BorderAdjacentIterator extends MapIterator {
        // The starting tile position
        private Position basePosition;
        // Index into the list of adjacent tiles
        private int index;

        /**
         * The constructor to use.
         * 
         * @param basePosition
         *            The position around which to iterate
         */
        public BorderAdjacentIterator(Position basePosition) {
            this.basePosition = basePosition;
            index = 1;
        }

        /**
         * Determine if the iterator has another position in it.
         * 
         * @return True of there is another position
         */
        public boolean hasNext() {
            for (int i = index; i < 8; i += 2) {
                Position newPosition = getAdjacent(basePosition, directions[i]);
                if (isValid(newPosition))
                    return true;
            }
            return false;
        }

        /**
         * Obtain the next position to iterate over.
         * 
         * @return Next position
         * @throws NoSuchElementException
         *             if last position already returned
         */
        @Override
        public Position nextPosition() throws NoSuchElementException {
            for (int i = index; i < 8; i += 2) {
                Position newPosition = getAdjacent(basePosition, directions[i]);
                if (isValid(newPosition)) {
                    index = i + 2;
                    return newPosition;
                }
            }
            throw new NoSuchElementException("Iterator exhausted");
        }
    }


    
    /**
     * Make the map usable as a parameter in the for-loop.
     * 
     * Returns all Tiles based on the order of the WholeMapIterator.
     * 
     * @return An Iterable that can be used to get an iterator for all tiles of the map.
     */
    public Iterable<Tile> getAllTiles() {
        return new Iterable<Tile>(){
            public Iterator<Tile> iterator(){
                final WholeMapIterator m = getWholeMapIterator();
                
                return new Iterator<Tile>(){
                    public boolean hasNext() {
                        return m.hasNext();
                    }

                    public Tile next() {
                        return getTile(m.next());
                    }

                    public void remove() {
                        m.remove();
                    }
                };
            }
        };
    }
}
